package 贪心;

import java.util.Arrays;

/**
 * @author admin
 * @version 1.0.0
 * @ClassName 分发糖果.java
 * @Description TODO
 * @createTime 2020年11月16日 22:46:00
 * 老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。
 *
 * 你需要按照以下要求，帮助老师给这些孩子分发糖果：
 *
 * 每个孩子至少分配到 1 个糖果。
 * 相邻的孩子中，评分高的孩子必须获得更多的糖果。
 * 那么这样下来，老师至少需要准备多少颗糖果呢？
 * 输入: [1,0,2]
 * 输出: 5
 * 解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。
 * 思路：贪心
 * 只需要来回两趟遍历即可 即在每次遍历的时候 只考虑更新同一侧的大小关系
 *
 */
public class 分发糖果 {
    class Solution {
        public int candy(int[] ratings) {
            if(ratings.length<0){
                return ratings.length;
            }
            int[] num=new int[ratings.length];
            Arrays.fill(num,1);
            for(int i=1;i<ratings.length;i++){
                if(ratings[i]>ratings[i-1]){
                    num[i]=num[i-1]+1;
                }
            }
            for(int i=ratings.length-1;i>0;i--){
                if(ratings[i]<ratings[i-1]){
                    num[i-1]=Math.max(num[i-1],num[i]+1);
                }
            }

            int res=0;
            for(int a:num){
                res+=a;
            }
            return res;
        }
    }
}
